package com.leetcode.LeetCode精选TOP面试题;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author 覃国强
 * @date 2022-06-21 18:44
 */
public class 题库_0127_单词接龙 {

  public static void main(String[] args) {
    String beginWord = "leet";
    String endWord = "code";
    List<String> wordList = new ArrayList<>(Arrays.asList("lest","leet","lose","code","lode","robe","lost"));

    Solution solution = new Solution();

    int length = solution.ladderLength(beginWord, endWord, wordList);
    System.out.println(length);
  }

  static
  class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
      if (wordList == null || wordList.isEmpty()) {
        return 0;
      }
      Set<String> set = new HashSet<>(wordList);
      if (!set.contains(endWord)) {
        return 0;
      }

      int answer = 1;
      Deque<String> cur = new ArrayDeque<>();
      Deque<String> next = new ArrayDeque<>();
      cur.add(beginWord);
      while (!cur.isEmpty()) {
        while (!cur.isEmpty() && !set.isEmpty()) {
          String curWord = cur.remove();
          Iterator<String> iterator = set.iterator();
          while (iterator.hasNext()) {
            String candidate = iterator.next();
            if (isMatch(curWord, candidate)) {
              if (endWord.equals(candidate)) {
                return answer + 1;
              }
              next.add(candidate);
              iterator.remove();
            }
          }
        }
        ++answer;
        Deque<String> temp = cur;
        cur = next;
        next = temp;
      }

      return 0;
    }

    private boolean isMatch(String word, String candidate) {
      if (word.length() != candidate.length()) {
        return false;
      }
      int diff = 0;
      for (int i = 0; i < word.length(); ++i) {
        if (word.charAt(i) != candidate.charAt(i)) {
          ++diff;
        }
        if (diff > 1) {
          return false;
        }
      }
      return true;
    }
  }

}
